package com.cwj.lab3.博客需要.dfs.迷宫问题;

import com.cwj.lab1.QueueCy;
import com.cwj.lab1.myArrayList;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MIGongPath {
    public MIGongPath(String path) {
        this.readGraph(path);
    }

    int[][]pic;
    private int xLen;
    private int yLen;
    private int num=0;
    final int[][]direction={{0,1},{1,0},{-1,0},{0,-1}};//右，下，上，左
    public  void readGraph(String path){
        try {
            Scanner in=new Scanner(new File(path));
            pic=new int[xLen=in.nextInt()][yLen=in.nextInt()];
            for (int i = 0; i < pic.length; i++) {
                for (int j = 0; j < pic[i].length; j++) {
                    pic[i][j]=in.nextInt();
                }
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public myArrayList<myArrayList<String>>getPath(int x,int y,int targetX,int targetY){
        if(pic==null)return null;
        myArrayList<myArrayList<String>>res=new myArrayList<>();
        myArrayList<String>list=new myArrayList<>();
        boolean[][]vis=new boolean[xLen][yLen];
        list.addLast("("+x+","+y+")");
        dfs(x,y,targetX,targetY,list,res,vis);
        return res;
    }

    private void dfs(int x,int y,int targetX,int targetY,myArrayList<String>list,myArrayList<myArrayList<String>>res,boolean[][]vis){
        if(x==targetX&&y==targetY){
            try {
                res.addLast((myArrayList<String>) list.clone());
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
            return ;
        }
        vis[x][y]=true;
        for (int i = 0; i < this.direction.length; i++) {
            int newX=x+this.direction[i][0];
            int newY=y+this.direction[i][1];
            if(newX<0||newY<0||newX>=this.xLen||newY>=this.yLen){
                continue;
            }
            if(!vis[newX][newY]&&pic[newX][newY]==1){
                list.addLast("("+newX+","+newY+")");
                dfs(newX,newY,targetX,targetY,list,res,vis);
                list.delLast();
            }
        }
        vis[x][y]=false;
    }
    public myArrayList<String> getOnePath(int x,int y,int targetX,int targetY){
        boolean[][]vis=new boolean[this.xLen][this.yLen];
        myArrayList<String>list=new myArrayList<>();
        this.getOnePath(x,y,targetX,targetY,list,vis);
        return list;
    }
    public boolean getOnePath(int x,int y,int targetX,int targetY,myArrayList<String>list,boolean[][]vis){
        if(x==targetX&&y==targetY){
            return true;
        }
        vis[x][y]=true;
        int newX=0,newY=0;
        for (int i = 0; i < this.direction.length; i++) {
            newX=x+this.direction[i][0];
            newY=x+this.direction[i][1];
            if(newX<0||newY<0||newX>=this.xLen||newX>=this.yLen){
                continue;
            }
            if(this.pic[newX][newY]==1&&!vis[newX][newY]){
                list.addLast("("+newX+" "+newY+")");
                if(getOnePath(newX,newY,targetX,targetY,list,vis)){
                    return true;
                }
            }
        }
        vis[x][y]=false;
        return false;
    }
    private static class Pair{
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public void minPath(int x,int y,Pair[][]parent,int[][]low){
        boolean[][]vis=new boolean[this.xLen][this.yLen];
        for (int i = 0; i < this.xLen; i++) {
            for (int j = 0; j < this.yLen; j++) {
                low[i][j]=-1;
                parent[i][j]=null;
            }
        }
        low[x][y]=0;
        QueueCy<Pair>que=new QueueCy<>();
        que.push(new Pair(x,y));
        Pair pr=null;
        int newX=0,newY=0;
        while(!que.isEmpty()){
            pr=que.pop();
            vis[pr.x][pr.y]=true;
            for (int i = 0; i < this.direction.length; i++) {
                newX=pr.x+this.direction[i][0];
                newY=pr.y+this.direction[i][1];
                if(newX<0||newY<0||newX>=this.xLen||newY>=this.yLen){
                    continue;
                }
                if(this.pic[newX][newY]==1&&!vis[newX][newY]){
                    parent[newX][newY]=new Pair(pr.x,pr.y);
                    low[newX][newY]=low[pr.x][pr.y]+1;
                    que.push(new Pair(newX,newY));
                }
            }
        }
    }
    public void showPath(Pair[][]parent,int[][]low){
        int xx=0,yy=0,temp=0;
        for (int i = 0; i < this.xLen; i++) {
            for (int j = 0; j < this.yLen; j++) {
                if(parent[i][j]==null){
                    continue;
                }
                System.out.print("{");
                System.out.print("("+i+" "+j+")");
                xx=parent[i][j].x;
                yy=parent[i][j].y;
                while(parent[xx][yy]!=null){
                    System.out.print("-->("+xx+" "+yy+")");
                    temp=parent[xx][yy].x;
                    yy=parent[xx][yy].y;
                    xx=temp;
                }
                System.out.print("-->("+xx+" "+yy+")");
                System.out.print("\tlow="+low[i][j]);
                System.out.println("}");
            }
        }
    }

    public int getxLen() {
        return xLen;
    }

    public int getyLen() {
        return yLen;
    }

    public static void main(String[] args) {
       MIGongPath mm=new MIGongPath("src/src/com/cwj/lab3/博客需要/dfs/迷宫问题/迷宫测试集");
        myArrayList<myArrayList<String>>table=mm.getPath(0,0,4,5);
        myArrayList<String>list=mm.getOnePath(0,0,4,5);
//        System.out.println("一条简单路径：");
//        list.show();
//        //System.out.println("11");
//        System.out.println("所有简单路径：");
//        for (int i = 0; i < table.size(); i++) {
//            table.get(i).show();
//        }
        Pair[][]parent=new Pair[mm.xLen][mm.yLen];
        int[][]low=new int[mm.xLen][mm.yLen];
        mm.minPath(2,3,parent,low);
        mm.showPath(parent,low);
    }
}
//测试
//Pair[][]parent=new Pair[mm.xLen][mm.yLen];
//int[][]low=new int[mm.xLen][mm.yLen];
//mm.minPath(2,3,parent,low);
//mm.showPath(parent,low);
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//{(0 0)-->(1 0)-->(1 1)-->(1 2)-->(2 2)-->(2 3)	low=5}
//{(0 3)-->(1 3)-->(2 3)	low=2}
//{(0 5)-->(1 5)-->(1 4)-->(1 3)-->(2 3)	low=4}
//{(1 0)-->(1 1)-->(1 2)-->(2 2)-->(2 3)	low=4}
//{(1 1)-->(1 2)-->(2 2)-->(2 3)	low=3}
//{(1 2)-->(2 2)-->(2 3)	low=2}
//{(1 3)-->(2 3)	low=1}
//{(1 4)-->(1 3)-->(2 3)	low=2}
//{(1 5)-->(1 4)-->(1 3)-->(2 3)	low=3}
//{(2 2)-->(2 3)	low=1}
//{(2 4)-->(2 3)	low=1}
//{(3 0)-->(3 1)-->(3 2)-->(2 2)-->(2 3)	low=4}
//{(3 1)-->(3 2)-->(2 2)-->(2 3)	low=3}
//{(3 2)-->(2 2)-->(2 3)	low=2}
//{(3 3)-->(2 3)	low=1}
//{(3 4)-->(3 3)-->(2 3)	low=2}
//{(4 0)-->(3 0)-->(3 1)-->(3 2)-->(2 2)-->(2 3)	low=5}
//{(4 1)-->(3 1)-->(3 2)-->(2 2)-->(2 3)	low=4}
//{(4 2)-->(3 2)-->(2 2)-->(2 3)	low=3}
//{(4 4)-->(3 4)-->(3 3)-->(2 3)	low=3}
//{(4 5)-->(4 4)-->(3 4)-->(3 3)-->(2 3)	low=4}